#include<string>
#include<vector>
#include<array>
#include<unordered_map>
#include<algorithm>
#include<limits>
#include <stack>
#include<iostream>
#include<sstream>
#include<deque>
#include<queue>
#include<set>
#include<unordered_set>
#define MOD 1000000007

struct  node
{
    int to;
    int weight;
    bool operator<(const node& other) const
    {
        return weight > other.weight;
    }
    node(int to, int weight):to(to),weight(weight){}
};
class Solution {
public:
    int networkDelayTime(std::vector<std::vector<int>>& times, int n, int k) {
        std::priority_queue<node> q;
        std::vector<std::vector<node>> adj(n+1,std::vector<node>());
        std::vector<bool> visited(n+1,false);
        std::vector<int> dist(n+1,std::numeric_limits<int>::max());
        int len =times.size();
        for(int i=0;i<len;i++)
        {
            adj[times[i][0]].emplace_back(times[i][1],times[i][2]);
        }
        dist[k]=0;
        q.emplace(k,0);
        while(!q.empty())
        {
            auto top = q.top();
            q.pop();
            if (visited[top.to]) continue;
            visited[top.to] = true;
            for (auto i : adj[top.to])
            {
                if (visited[i.to]) continue;
                if (top.weight + i.weight<dist[i.to])
                {
                    dist[i.to] = top.weight + i.weight;
                    q.emplace(i.to,dist[i.to]);
                }
            }
        }
        int m = 0;
        for (int i = 1; i <= n; i++)
        {
            if (dist[i]==std::numeric_limits<int>::max()) return -1;
            m = std::max(m,dist[i]);
        }
        return m;
    }
};
